package algorithms.sort;

import java.util.PriorityQueue;

/**
 * 堆排序
 * 时间复杂度：O(N*logN)
 * 额外空间复杂度：O(1)
 * ===================讲解=======================
 * 数组:[3,5,2,7,1,9,6]
 * 下标: 0 1 2 3 4 5 6
 * 对应完全二叉树(下标表示):
 *         0
 *        /\
 *       1  2
 *      /\  /\
 *     3 4 5  6
 *
 * 堆（完全二叉树）结构使用数组存储的关系,i下标：
 *      1.父节点下标：(i-1)/2；
 *      2.左孩子下标：2*i+1；
 *      3.右孩子下标：2*i+2；
 * 堆的分类:
 * 大根堆: 每棵子树的最大值都在顶部
 * 小根堆: 每棵子树的最小值都在顶部
 *
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = GetRandomArr.getRandomArr(10);
        //heapSort(arr);
        //System.out.println("数组:==>"+ Arrays.toString(arr));


        // PriorityQueue底层就是默认小根堆
//        PriorityQueue<Integer> queue = new PriorityQueue();
        //for (int e : arr) {
        //    queue.add(e);
        //}
        //while (!queue.isEmpty()) {
        //    System.out.println(queue.poll());
        //}
    }


    /**
     * 堆排序
     * 思路：
     *     1. 将元素插入到大根堆中；
     *     2. 依次堆中第一个元素（堆中的最大值）和堆最后一个元素交换，堆大小减一，并维护大根堆结构，
     *     直到堆空间为0；
     *
     * @param arr
     */
    private static void heapSort(int[] arr) {
        if(arr == null || arr.length <=1)
            return;
        // =====步骤一
        // 堆空间大小
        //int heapSize = 0;
        // 对数组整体以此插入到堆中,heapSize++
        //for (int i = 0; i< arr.length; i++,heapSize++)
        //    heapInsert(arr,i); // O(logN)

        // 步骤一优化版:从最后一位开始进行子树的heapify,形成堆,以此向上知道整颗树是堆。
        int heapSize = arr.length;
        for (int i = arr.length-1;i >= 0;i--) {// O(N)
            heapify(arr,i, heapSize);
        }

        // =====步骤二
        // 取出堆中第一个位置元素（最大值）放到数组末尾,堆大小heapSize--;
        swap(arr,0,--heapSize);
        while (heapSize > 0) {// 直到堆中元素全部取出
            // 从根节点开始 大根堆化
            heapify(arr,0,heapSize);
            // 取出堆中第一个位置元素（最大值）放到数组末尾
            swap(arr,0,--heapSize);
        }
    }

    public static void swap(int[] arr, int i,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 元素插入到大根堆中，并保持大根堆结构
     *
     * 思路：当前位置的值与父节点的值比较
     *      若前位置的值大于节点的值，交换值，index来到父节点位置，向上比较，直到根节点位置，完成大根堆化。
     *      若前位置的值小于节点的值，完成大根堆化。
     *
     * @param arr
     * @param index ：当前下标
     */
    public static void heapInsert(int[] arr,int index) {
        // 1.当前位置的数大于父节点位置的数，2.并且会一直比较到根节点(index = 0会停)
        while (arr[index] > arr[(index - 1) / 2]) {
            // 当前位置的数 和 父节点位置的数 交换
            swap(arr,index,(index - 1) / 2);
            // index 来到父节点
            index = (index - 1) / 2;
        }
    }

    /**
     * 从当前位置开始，使自己和孩子大根堆化。
     * 思路：当前位置与自己的最大孩子比较
     *      若当前位置的值小于最大孩子，交换值，index来到最大孩子位置,向下比较，直到没有孩子为止，完成大根堆化
     *      若当前位置的值大于最大孩子，完成大根堆化。
     *
     * @param arr
     * @param index ：当前位置
     * @param heapSize ：堆大小
     */
    public static void heapify(int[] arr,int index,int heapSize) {
        // 左孩子
        int left = 2 * index + 1;
        // index节点有孩子（左孩子不越界，必有孩子）
        while (left < heapSize) {
            // 1.左右孩子比较大小，较大的孩子的下标给largest;(left + 1 = 右孩子下标)
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ?
                    left + 1 : left;
            // 2.父亲与孩子比较大小，较大的下标给largest;
            largest = arr[index] > arr[largest] ? index : largest;
            // 3.如果最大值是父本身，完成heapify;
            if (largest == index)
                break;
            // 否则，交换父亲与孩子的数值
            swap(arr,index,largest);
            // index 来到新的孩子位置
            index = largest;
            // 新的左孩子
            left = 2 * index + 1;
        }
    }
}
